import collections
from typing import List


class Solution:
    def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:
        graph = collections.defaultdict(set)

        for i in range(nodes):
            graph[parent[i]].add(i)

        root = graph[-1].pop()

        def dfs(node):
            """返回 剩余节点数,和"""
            num0 = 1
            val0 = value[node]

            for nxt in graph[node]:
                num1, val1 = dfs(nxt)
                num0 += num1
                val0 += val1

            if val0 == 0:
                return 0, 0
            else:
                return num0, val0

        return dfs(root)[0]


if __name__ == "__main__":
    print(Solution().deleteTreeNodes(nodes=7, parent=[-1, 0, 0, 1, 2, 2, 2], value=[1, -2, 4, 0, -2, -1, -1]))  # 2
    print(Solution().deleteTreeNodes(nodes=7, parent=[-1, 0, 0, 1, 2, 2, 2], value=[1, -2, 4, 0, -2, -1, -2]))  # 6
    print(Solution().deleteTreeNodes(nodes=5, parent=[-1, 0, 1, 0, 0], value=[-672, 441, 18, 728, 378]))  # 5
    print(Solution().deleteTreeNodes(nodes=5, parent=[-1, 0, 0, 1, 1], value=[-686, -842, 616, -739, -746]))  # 5
